/*
 * @lc app=leetcode.cn id=911 lang=golang
 *
 * [911] 在线选举
 */

// @lc code=start
type TopVotedCandidate struct {
	persons   []int
	times     []int
	winPerson []int
}

func Constructor(persons []int, times []int) TopVotedCandidate {
	win := make([]int, len(persons))
	// 维护一个数组，保存该点获胜的人
	countPerson := make([]int, len(persons))
	// 维护当前时间及之前最多的选票数
	max := 1
	// 维护当前及之前选票最多的人
	maxPerson := persons[0]
	for i := 0; i < len(persons); i++ {
		countPerson[persons[i]]++
		if countPerson[persons[i]] >= max {
			max = countPerson[persons[i]]
			maxPerson = persons[i]
		}
		win[i] = maxPerson
	}
	//fmt.Println(win)
	return TopVotedCandidate{persons, times, win}
}

func (this *TopVotedCandidate) Q(t int) int {
	left := 0
	right := len(this.times) - 1
	// 二分查找，查找t时间或之前的索引
	for left < right {
		mid := (left + right) / 2
		if this.times[mid] >= t {
			right = mid
		} else {
			left = mid + 1
		}
	}
	// 当right处的时间大于t时，有效的时间为right之前的时间
	if this.times[right] > t {
		right--
	}
	return this.winPerson[right]
}

/**
 * Your TopVotedCandidate object will be instantiated and called as such:
 * obj := Constructor(persons, times);
 * param_1 := obj.Q(t);
 */
// @lc code=end

